/**
 *
 * <p>Knapsack Problem.</p>
 *
 * <p>Input: $n$ item types {$a_1, ..., a_n$}. Each item type $a_i$ has size $s_i$ and profit $p_i$. Knapsack capacity is $B$.</p>
 * <p>Goal: find optimal subset of objects whose total size is bounded by $B$ and has maximum possible total profit.</p>
 *
 * $$\table \text"Maximize ",: , ∑↙{i=1}↖np_ix_i;
 * \text"subject to ",: , ∑↙{i=1}↖ns_ix_i ≤ B;
 * \text"where ",: , {p_i &gt; 0, s_i &gt; 0, B &gt; 0, x_i ∈ ℤ*}$$
 *
 * <p>There are three types of knapsack problem:</p>
 * <ul>
 *     <li>Binary knapsack (or 0/1 knapsack): $x_i ∈ \{0, 1\}$</li>
 *     <li>Bounded knapsack: $0 ≤ x_i ≤ b_i$</li>
 *     <li>Unbounded knapsack: $x_i ≥ 0$</li>
 * </ul>
 *
 * <p>Knapsack problems are NP-hard problems. The problem is reduced to integer linear programming because $x_i ∈ ℤ*$.</p>
 *
 * <p>If the integrality constraint of $x_i$ is removed, the problem becomes continuous knapsack problem and can be easily
 * solved using greedy algorithm. For example, instead of objects, there are liquid material to pack into the knapsack.</p>
 *
 * <p>There are pseudo-polynomial algorithms to find exact optimal solution if $s_i ∈ ℤ+$ or $p_i ∈ ℤ+$ using dynamic programming.
 * If $s_i ∈ ℤ+$, assume $B ∈ ℤ+$ (otherwise round down $B$ because $∑s_ix_i ∈ ℤ*$), the pseudo-polynomial
 * running time is $O(nB)$. If $p_i ∈ ℤ+$, the pseudo-polynomial running time is $O(nP)$ where $P = ∑p_i$. These
 * algorithms are pseudo-polynomial because $B$ and $P$ can be very large.</p>
 *
 *
 * <h3>Approximation for 0/1 knapsack problem.</h3>
 * <p>As $O(nB)$ and $O(nP)$ can be extremely large, we can approximate the solution by removing the dependency $P$.</p>
 *
 * <p>To scale down the profit: let $k = { ε⋅p_{max} }/n$. This will make the largest $p_i ≈ n/ε$. Scale down the profit
 * of each item $p_i' = ⌊ p_i / k ⌋$. Let $P' = ∑p_i' ≤ ∑p_i/k ≤ ∑p_{max}/k = ∑n/ε = n^2/ε$. The problem becomes:
 * $$\text"Maximize " ∑↙{i=1}↖np_i'x_i \text" subject to " ∑↙{i=1}↖ns_ix_i ≤ B$$
 * Using the above dynamic programming, the running time is $O(nP') ≤ O(n^3/ε)$.
 * </p>
 * <p>Let $\{x_1*, ..., x_n*\}$ be the optimal solution and $\{x_1', ..., x_n'\}$ be the solution found by the approximate algorithm.
 * Let $P* = ∑p_ix_i*, P*' = ∑p_i'x_i*, A' = ∑p_i'x_i', A = ∑p_ix_i'$. Assume $s_i ≤ B$ (otherwise exclude $a_i$ from the problem)
 * $⇒ p_i ≤ P*$ (otherwise $x_ip_i$ would have been the solution).
 * Proof that $A ≥ (1-ε)⋅P*$:
 * $$\table p_i' ,≤, p_i / k ,≤, p_i' + 1;
 *          k⋅p_i' ,≤, p_i ,≤, k⋅p_i' + k$$
 * $$\table
 *              P*  ,≤, k⋅P*' + nk ,∵, p_i ≤ k⋅p_i' + k;
 *                  ,≤, k⋅A' + nk;
 *                  ,≤, A + nk ,∵, k⋅p_i' ≤ p_i;
 *                  ,=, A + ε⋅p_{max};
 *                  ,≤, A + ε⋅P* ,∵, p_i ≤ P* ;
 *               A  ,≥, (1-ε)⋅P*
 *               $$
 * </p>
 *
 *
 *
 * <h3>Variations</h3>
 * <p>Opposite knapsack problem.</p>
 * <p>Input: $n$ item types {$a_1, ..., a_n$}. Each item type $a_i$ has size $s_i$ and profit $p_i$.</p>
 * <p>Goal: find subset of objects whose total size is at least $B$ and has minimum total profit.</p>
 *
 * @author Trung Phan
 *
 */
package net.tp.algo.knapsack;
